import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 言初
 * Date: 2023-01-13
 * Time: 21:14
 */
public class Test {
    public List<List<Integer>> generate(int numRows) {
        // 杨辉三角
        List<List<Integer>> ret = new ArrayList<>();
        List<Integer> row = new ArrayList<>();
        row.add(1);
        ret.add(row);
        for (int i = 1; i < numRows; i++) {
            List<Integer> prevRow = ret.get(i-1);//前一行
            List<Integer> curRow = new ArrayList<>();
            curRow.add(1);//第一个1
            //中间curRow list的赋值
            for (int j = 1; j < i; j++) {
                int x = prevRow.get(j)+prevRow.get(j-1);
                curRow.add(x);
            }
            curRow.add(1);//最后一个1
            ret.add(curRow);
        }
        return ret;
    }


    public List<List<Integer>> generate1(int numRows) {
        // 杨辉三角
        List<Integer> list=new ArrayList<>();
        List<List<Integer>> array=new ArrayList<>();
        list.add(1);
        array.add(list);

        for(int i=1;i<numRows;i++){
            List<Integer> prevList=new ArrayList<>();
            List<Integer> curList=new ArrayList<>();
            for(int j=0;j<=i;j++){
                prevList=array.get(i-1);
                if(j==0||i==j){
                    curList.add(1);
                }else{
                    int num=prevList.get(j)+prevList.get(j-1);
                    curList.add(num);
                }
            }
            array.add(curList);
        }
        return array;
    }

    public static void main1(String[] args) {
        Test list=new Test();
        List<List<Integer>> array=list.generate1(4);
        System.out.println(array);
    }







    public static void main2(String[] args) {
        int[] array={1,8,6,2,5,4,8,3,7};
        int count=maxArea(array);
        System.out.println(count);
    }
    public static int maxArea(int[] height) {
        int count=0;
        int i=0;
        int j=height.length-1;
        while(i<j){
            int ret;
            if(height[i]<height[j]){
                ret=height[i]*(j-i);
                i++;
            }else{
                ret=height[j]*(j-i);
                j--;
            }
            if(ret>count){
                count=ret;
            }
        }
        return count;
    }






    public static void main3(String[] args) {
        String  s = "IVIV";
        System.out.println(romanToInt(s));
    }
    public static int romanToInt(String s) {
        //罗马数字转整数  正确
        //  I， V， X， L，C，D  M
        /*I             1
        V             5
        X             10
        L             50
        C             100
        D             500
        M             1000*/
        //记得处理特殊情况，而且特殊情况每个应该只能出现一次，
        //因为还有一个规则在里面：
        //通常情况下，罗马数字中小的数字在大的数字的右边，除了那6个特例
        int count=0;
        for (int i = 0; i < s.length(); i++) {
            char ch=s.charAt(i);

            if(ch=='I'){
                int j=i+1;
                if(j<s.length()&& s.charAt(j)=='V'){
                    count+=4;
                    i++;
                }else if(j<s.length()&& s.charAt(j)=='X'){
                    count+=9;
                    i++;
                }else{
                    count+=1;
                }
            }else if(ch=='V'){
                count+=5;
            }else if(ch=='X'){
                int j=i+1;
                if(j<s.length()&& s.charAt(j)=='L'){
                    count+=40;
                    i++;
                }else if(j<s.length()&& s.charAt(j)=='C'){
                    count+=90;
                    i++;
                }else{
                    count+=10;
                }
            }else if(ch=='L'){
                count+=50;
            }else if(ch=='C'){
                int j=i+1;
                if(j<s.length()&& s.charAt(j)=='D'){
                    count+=400;
                    i++;
                }else if(j<s.length()&& s.charAt(j)=='M'){
                    count+=900;
                    i++;
                }else{
                    count+=100;
                }
            }else if(ch=='D'){
                count+=500;
            }else if(ch=='M'){
                count+=1000;
            }
        }
        return count;
    }







    public static void main4(String[] args) {
        int num=3337;
        System.out.println(intToRoman(num));
    }
    public static String intToRoman(int num) {
        //   罗马数字中小的数字在大的数字的右边
        //   我的想法就是得到这个数字的各个位上的数字，然后再分别表示
        //   各个位从1到9的各个字符表示形式
        //   总体遵循的原则是：罗马数字中小的数字在大的数字的右边
        //   所以说这些字符的大小关系就是：从大到小
        //   M(1000)  CM(900)  D(500)  CD(400)  C(100)  XC(90)  L(50)
        //   XL(40)   X(10)  IX(9)  V(5)  IV(4)  I(1)
        // 所以说：在表示各个数字的符号表示时：一般情况下那6种特殊的情况每个都只能使用一次
        // 而且还得按照大小的顺序来使用

        StringBuffer str = new StringBuffer("");
        int ret=0;
        int count=num;
        //题目已经保证 ：1 <= num <= 3999
        int con=0;
        for (int i = 1; i <= 4; i++) {
            //str.append("kl");
            if(i==1){     //  千位
                con=1000;
                ret=count/con;
                count=count%con;
                while(ret>0){
                    str.append('M');
                    ret--;
                }
            }else if(i==2){  //  百位  （从100到900）
                con=100;
                ret=count/con;
                count=count%con;
                // 900  500  400  100
                if(ret==9){
                    str.append("CM");
                }else if(ret==5){
                    str.append('D');
                }else if(ret==4){
                    str.append("CD");
                }else if(ret==1){
                    str.append('C');
                }else if(ret==6){
                    str.append("DC");
                }else if(ret==2){
                    str.append("CC");
                }else if(ret==3){
                    str.append("CCC");
                }else if(ret==7){
                    str.append("DCC");
                }else if(ret==8){
                    str.append("DCCC");
                }

            }else if(i==3){  //  十位 （从10到90）
                con=10;
                ret=count/con;
                count=count%con;
                if(ret==9){
                    str.append("XC");
                }else if(ret==5){
                    str.append('L');
                }else if(ret==4){
                    str.append("XL");
                }else if(ret==1){
                    str.append('X');
                }else if(ret==6){
                    str.append("LX");
                }else if(ret==2){
                    str.append("XX");
                } else if (ret==3){
                    str.append("XXX");
                }else if (ret==7){
                    str.append("LXX");
                }else if(ret==8){
                    str.append("LXXX");
                }
            }else if(i==4){  //  个位 （从1到9 ）
                con=1;
                ret=count/con;
                count=count%con;
                if(ret==9){
                    str.append("IX");
                }else if(ret==5){
                    str.append('V');
                }else if(ret==4){
                    str.append("IV");
                }else if(ret==1){
                    str.append("I");
                }else if(ret==6){
                    str.append("VI");
                }else if(ret==2){
                    str.append("II");
                }else if(ret==3){
                    str.append("III");
                }else if(ret==7){
                    str.append("VII");
                }else if (ret==8){
                    str.append("VIII");
                }
            }
        }
        return str.toString();
    }







    public static void main5(String[] args) {
        int[] nums={1,2,4,4,5,6};
        int[] array=searchRange(nums,4);
        System.out.println(array[0]);
        System.out.println(array[1]);
    }

    public static int[] searchRange(int[] nums, int target) {
        // 先二分查找一下，找到中间的那个等于target的坐标
// 然后从它的左边和右边分别去找看看还有没有
// 递归思想
//
        //要求时间复杂度是 ： O(log n)
        int[] array={-1,-1};
        if(nums.length==0){
            return array;
        }
        return array;
    }






    public void rotate(int[][] matrix) {

    }



    public static void main6(String[] args) {
Test inc = new Test();
 int i = 0;
  inc.fermin(i);
  //重点是这里：它 i= i++; 是后置加加，这样的话就是先使用后加加，所以i应该等于0，然后i不应该在加加了吗？？？？？？？？？
 i= i++;
 System.out.println(i);

  }
void fermin(int i){
        //对于这个函数，是没有改变main中i的值的，它也并没有返回值之类的东西
  i++;
 }






    public static void main(String[] args) {

    }







    public int countAsterisks(String s) {
        // 统计星号(力扣的题）
        //注意，每个竖线 '|' 都会 恰好 属于一个对。
        //上面的这个是一个很好的条件，就是说一定会有偶数个竖线’|‘
        int length=s.length();
        int ret=0; //统计竖线’|‘是否配对，如果配对了，ret就会等于2
        int count=0; //统计 * 的个数
        for(int i=0;i<length;i++){
            char ch=s.charAt(i);
            if(ch=='|'){
                ret++;
                if(ret==2){
                    ret=0;
                }
            }else{
                if(ret==0&&ch=='*'){
                    count++;
                    // 如果ret==0,就说明此时访问的字符不在竖线对之间
                    // 就可以进行下一步，看ch是否是 * 了
                }
            }
        }
        return count;
    }
}




